package com.mlamp.二叉树;

import com.alibaba.fastjson.JSONObject;

import javax.sound.sampled.Line;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class 二叉树和为某一值的路径 {

    public static void main(String[] args) {
        二叉树和为某一值的路径 instance = new 二叉树和为某一值的路径();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        List<List<Integer>> lists = instance.pathSum2(root, 22);
        for (List<Integer> item : lists) {
            System.out.println(Arrays.toString(item.toArray()));
        }
        lists = instance.pathSumC(root, 22);
        Set<List<Integer>> distinct = lists.stream().distinct().collect(Collectors.toSet());
        System.out.println(JSONObject.toJSONString(distinct));
    }

    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    public List<List<Integer>> pathSum2(TreeNode root, int sum) {
        recur2(root, sum);
        return res;
    }

    public List<List<Integer>> pathSumC(TreeNode root, int sum){
        recurC(root, sum);
        return res;
    }


    void recur4(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }


    void recur6(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recur6(root.left, target);
        recur6(root.right, target);
        path.removeLast();
    }

    void recur5(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }


    void recur3(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }


    void recur2(TreeNode root, int tar) {
        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }


    void recur(TreeNode root, int tar) {
        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }

    void recurA(TreeNode root, int tar) {
        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recurA(root.left, tar);
        recurA(root.right, tar);
        path.removeLast();
    }


    public void recurB(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recurB(root.left, target);
        recurB(root.right, target);
        path.removeLast();
    }


    public void recurC(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recurC(root.left, target);
        recurC(root.right, target);
        path.removeLast();
    }


}
